#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "TypeDefin.h"

using namespace std;
/*
 * 501. 二叉搜索树中的众数
简单
566
相关企业
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
 *
 *
 *
 * **/
// 因为是二叉树 所以满足 条件 中序遍历是一个有序序列
//todo 做题的时候脑子有点不清行
vector<int> res;
TreeNode *pre = nullptr;
int count;
int maxV;

void dfs(TreeNode *root) {
    if (!root)
        return;

    dfs(root->left);

    if (pre == nullptr) {
        pre = root;
        count = 1;
        res.push_back(root->val);
    } else if (pre->val == root->val) {
        count++;

    } else {
        count = 1;

    }

    if (maxV == count) {
        res.push_back(root->val);
    } else if (maxV < count) {
        maxV = max(maxV, count);
        res.clear();
        res.push_back(root->val);
    }


    pre = root;

    dfs(root->right);

}

vector<int> findMode(TreeNode *root) {

    dfs(root);
    return res;
}
